package _11_整理题目._4_动态规划._硬币找零;

import org.junit.Test;

/**
 * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
 * 请你计算并返回 可以凑成总金额的硬币组合数。
 * 如果任何硬币组合都无法凑出总金额，返回 0 。
 * 假设每一种面额的硬币有无限个。
 *
 *
 */
public class _02_凑成目标的硬币总种类 {

    public int change(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i < amount+1; i++) {
                dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }

    @Test
    public void main() {
        int[] coins = {1, 2, 5};
        System.out.println(change(coins, 5));
    }
}
